package org.jcat.toolkit.datatypex;
/**
 * 优化的双向链表，头节点代表第1个元素。
 * 节点序号从0开头
 * @author hejinxu
 *
 */
public class DoubleLinkedList {
    class Node {// 节点元素
        public Node prev;
        public Object value;
        public Node next;

        boolean isHeader(Object o) {
            if (o == header) {
                return true;
            }
            return false;
        }
    }

    private Node header = null;

    public void insert(Object n) {
        Node e = new Node();
        e.value = n;
        if (header == null)// 说明这是第一次插入元素
        {
            header = e;
            header.next = e;
            header.prev = e;
            e.prev = e;
            e.next = e;
            return;
        }

        // 在最后插入元素
        e.next = header;
        e.prev = header.prev;
        header.prev.next = e;
        header.prev = e;

    }

    public void insert(int i, Object n)// 在链表的i位置插入元素n
    {
        if (i < 0) {
            System.out.println("插入位置不合法！！！" + "链表长度为:" + size());
            return;
        }

        Node e = new Node();
        e.value = n;
        // 说明这是第一次插入元素，在头结点后面插入元素
        if (header == null) {
            e.prev = e;
            e.next = e;
            header = e;
            header.next = e;
            header.prev = e;
            return;
        } 

        // 在最后插入元素
        if (i >= size()) {
            e.prev = header.prev;
            e.next = header;
            header.prev.next = e;
            header.prev = e;
            return;
        }

        if (i == 0) {   //在头节点插入
            e.next = header;
            e.prev = header.prev;
            header.prev.next = e;
            header.prev = e;
            header = e;
            return;
        }

        // 在i位置插入元素
        Node temp = header;
        int count = 0;
        while (temp.next != header) {
            count++;
            if (count == i) {
                e.next = temp.next;
                e.prev = temp;
                temp.next.prev = e;
                temp.next = e;

            }
            temp = temp.next;
        }
    }

    public Node getNode(int i) {
        if (header == null) {
            return null;
        }

        if (i < 0 || i >= size()) {
            System.out.println("输入数据有错！");
            return null;
        }

        int count = -1;
        Node temp = null;
        while (true) {
            count++;
            if (temp == null) {
                temp = header;
            }

            if (count == i) {
                break;
            }

            if (temp.next != header) {
                temp = temp.next;
            } else {
                break;
            }
        }
        return temp;
    }

    public Object getNodeVal(int i) {
        Node n = getNode(i);
        if (n != null) {
            return n.value;
        }
        return null;
    }

    public int size()// 返回链表的长度
    {
        if (header == null) {
            return 0;
        }

        int count = 0;
        Node temp = header;
        while (true) {
            count++;
            if (temp.next == header) {
                break;
            }
            temp = temp.next;
        }
        return count;
    }

    public void printList() {
        if (header == null) {
            return;
        }
        Node temp = header;
        while (true) {
            System.out.print(temp.value + " ");
            temp = temp.next;
            if (temp == header) {
                break;
            }
        }
        System.out.println();
    }

    public void deleteByIndex(int i)// 删除指定位置上的元素
    {
        if (i < 0 || i >= size()) {
            System.out.println("删除的位置误" + "链表长度为:" + size());
        }

        Node e = getNode(i);
        if (e == header) {

            //当只有一个元素时
            if (e.next == header) {
                header = null;
                return;
            }

            //当只有两个元素时
            if (e.prev == e.next) {
                e.next.next = e.next;
                e.next.prev = e.next;
                header = e.next;
                e = null;
                return;
            }

            //当不止两个元素时
            e.prev.next = e.next;
            e.next.prev = e.prev;
            header = e.next;
            return;

        }

        //当删除的不是头节点时
        e.prev.next = e.next;
        e.next.prev = e.prev;
    }

    public void deleteByEle(Object element)// 删除链表中指定元素
    {

    }
    
}